'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-26 16:12:55
'''
'''
5474. 好叶子节点对的数量
给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

 

示例 1：

 



输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：



输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：

输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：

输入：root = [100], distance = 1
输出：0
示例 5：

输入：root = [1,1,1], distance = 2
输出：1


tips:dfs递归，这个题的关键是怎么找到计算距离的方法。一个list记录访问节点的页节点到它的距离，
两个叶节点之间的距离用该节点的左右两部分叶节点的距离和表示
'''

from typing import List
from tree_node import *
class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:

        def recurse(root, ans):
            if not root:
                return []
            if not root.left and not root.right:
                return [0]
            re = []
            left = recurse(root.left, ans)
            for i in left:
                if i>distance:
                    continue
                re.append(i+1)
            right = recurse(root.right, ans)
            for i in right:
                if i>distance:
                    continue
                re.append(i+1)
            for l in left:
                for r in right:
                    if l+r+2<=distance:
                        ans[0] += 1
            return re
        ans = [0]
        recurse(root, ans)
        return ans[0]

if __name__ == "__main__":
    solution = Solution()
    null = 'null'
    root = [1,2,3,4,5,6,7]
    distance = 3
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    print(solution.countPairs(root, distance))